Search for: All records

We present a new class of preconditioned iterative methods for solving linear systems of the form Ax = b. Our methods are based on constructing a low-rank Nyström approximation to A using sparse random matrix sketching. This approximation is used to construct a preconditioner, which itself is inverted quickly using additional levels of random sketching and preconditioning. We prove that the convergence of our methods depends on a natural average condition number of A, which improves as the rank of the Nyström approximation increases. Concretely, this allows us to obtain faster runtimes for a number of fundamental linear algebraic problems: 1. We show how to solve any n × n linear system that is well-conditioned except for k outlying large singular values in Õ (n2.065 + kω) time, improving on a recent result of [Derezmski, Yang, STOC 2024] for all k ≳ n0.78. 2. We give the first Õ (n2 + dλω) time algorithm for solving a regularized linear system (A+λΙ)x = b, where A is positive semidefinite with effective dimension dλ = tr(A(A + λΙ)-1). This problem arises in applications like Gaussian process regression. 3. We give faster algorithms for approximating Schatten p-norms and other matrix norms. For example, for the Schatten 1-norm (nuclear norm), we give an algorithm that runs in Õ (n2.11) time, improving on an Õ (n2.18) method of [Musco et al., ITCS 2018]. All results are proven in the real RAM model of computation. Interestingly, previous state-of-the-art algorithms for most of the problems above relied on stochastic iterative methods, like stochastic coordinate and gradient descent. Our work takes a completely different approach, instead leveraging tools from matrix sketching. 

Abstract The Eastern Himalayan Syntaxis (EHS) is one of the fastest exhuming regions on Earth since ∼10 Ma, and the mechanism of its fast exhumation is under debate. Different from many other studies based on tectonics‐driven models, we performed analytical analysis and numerical simulations to investigate an erosion‐driven system. Our results show that fast and focused surface erosion alone is able to exhume the lower crust on the timescale of ∼10 Myr. This process leads to the formation of a domal structure, an elevated geothermal gradient, rapid cooling of crustal rocks, and decompression melting in the lower crust. In the upper‐mid crust, the uplift of crustal rocks is caused by isostatic flow driven by pressure gradient, whose rate is limited by the driving erosional forcing. In the mid‐lower crust where decompression melting occurs, rocks entrained in a buoyant diapir experience fast uplift rate exceeding the erosional forcing. Our erosion‐driven model demonstrates an intricate coupling between surface erosion and crustal processes. Positive feedback between surface erosion and rock uplift is possible under certain conditions and crustal diapirism plays a key role in the feedback. Our study shows that both isostatic and diapiric flows play important roles in the uplift and exhumation of crustal rocks in the EHS. We highlight that erosion‐driven crustal diapirism can be one of the missing pieces explaining the evolution of the Eastern Himalayan Syntaxis.